﻿#include<iostream>
#include <ctime>
using namespace std;

typedef unsigned long long ullong; //%lld
typedef unsigned __int64 uint64;  //%I64d,%I64u

void print(int* list, int n){
    printf("[");
    for(int i=0; i<n; i++) {
        printf("%d,", list[i]);
    }
    printf("]\n");
}

//找出数组中唯一的重复元素
//
//详细描述见findrepeat.py

//n = 1000001, read = 0.543000s
//(method,time,result):
//1 0.001000s 543862
//2 0.000000s 543862
//4 0.030000s 543862
//3 0.017000s 543862

//n = 10000001, read = 5.912000s
//(method,time,result):
//1 0.007000s 1349842
//2 0.007000s 1349842
//4 0.938000s 1349842
//3 0.366000s 1349842
int findRepeat_1(int* list, int n){
    uint64 sum = 0;
    for(int i=0; i<n; i++) {
        sum += list[i];
    }
    uint64 un = uint64(n);
    return sum - un*(un-1)/2;
}

int findRepeat_2(int* list, int n){
    int r = 0;
    for(int i=0; i<n; i++) {
        r = r^list[i]^i;
    }
    return r;
}

//C的版本 时间没有很不稳定
int findRepeat_3(int* list, int n){
    int i=0;
    while(true) {
        if(list[i]<0) break;
        list[i] = -list[i];
        i = -list[i];
    }
    return i;
}

int findRepeat_4(int* list, int n){
    int s=0, f=0;
    while(true) {
        s = list[s];
        f = list[list[f]];
        if(s==f) break;
    }
    f=0;
    while(true) {
        s = list[s];
        f = list[f];
        if(s==f) break;
    }
    return s;
}

struct Elapse
{
    clock_t start;
    Elapse():start(clock()){}
    double get() {
        return (double)(clock()-start)/CLOCKS_PER_SEC;
    }
    void reset(){start=clock();}
};

int main()
{
    //freopen("o.txt", "r", stdin);
    int n;
    scanf("%d", &n);
    int* list = new int[n];
    //read input
    Elapse e;
    for(int i=0; i<n; i++) {
        scanf("%d", &list[i]);
    }
    double t = e.get();
    printf("n = %d, read = %.6fs\n", n, t);
    if(n<=50) print(list, n);
    printf("(method,time,result):\n");

    //finding
    e.reset();
    int res = findRepeat_1(list, n);
    t = e.get();
    printf("1 %.6fs %d\n", t, res);

    e.reset();
    res = findRepeat_2(list, n);
    t = e.get();
    printf("2 %.6fs %d\n", t, res);

    e.reset();
    res = findRepeat_4(list, n);
    t = e.get();
    printf("4 %.6fs %d\n", t, res);

    e.reset();
    res = findRepeat_3(list, n);
    t = e.get();
    printf("3 %.6fs %d\n", t, res);

    delete []list;
    return 0;
}